In contradistinction to widespread memory arrays, such as a Random Access Memory (RAM) that stores and retrieves data segments indexed by their address, Content Addressable Memories (CAMs) are types of Associative Memories that contain associative data (also termed “Keys”) and data that is associated with these Keys (also termed “Associated Data”). A CAM stores the Keys and the Associated Data at an available location, and retrieves the data associated with a specific key by “searching” the content of that specific Key.
Typical applications utilizing CAMs are, for example, language-translation, face (e.g., of a credit card owner) or fingerprint recognition, data retrieval from a database, part inspection, etc. These types of applications can be carried out faster and more accurately using CAMs. However, currently available CAMs are small in their capacity, expensive, slow in their associated data retrieval speed, consume a substantial amount of power and are rarely used, while RAMs are large in size, inexpensive, fast and ubiquitous. Therefore, a CAM integrated circuit (chip) that is intuitive, fast, of high density and low power, and inexpensive is highly desired. In addition, intuitive and fast operation normally requires the Key being concurrently searched in all the CAM locations. Conventional CAM implementations require concurrent comparison operations performed in each memory cell. This results in a more expensive, larger, slower and high-power consuming CAM, in comparison to a RAM implemented using the same technology.
In order to reduce the CAM cost, efforts were made in several directions. For example, an effort was directed towards a solution that combines hardware and software. Software data structures, databases, neural networks, and other contrivances were sought to make RAMs operate in an associative manner. However, these solutions resulted in relatively slow search operation, because each associative reference typically requires many RAM accesses and processor cycles. Nevertheless, for many applications, the combination of a fast processor and a fast RAM has been sufficient. However, many other applications natural for CAMs, especially those which require massive amounts of memory, have not yet been developed because a sufficiently fast, dense, large and inexpensive CAM is unavailable.
Few applications, such as in data communications use CAMs since a RAM, combined with a software shell, cannot meet the speed requirements when associative lookups are required. In spite of the several improvements in the CAM density and speed, the inherent density problems, coupled with higher cost, restrict the use of CAMs to applications, such as data-packet routing and switching, where the lookup speed is the most critical factor. The conventional basic CAM cell circuit complexity remain the major obstacle for efficient CAM implementation, and therefore currently available CAMs are still expensive, have low performance and consume high power.
UTMC (USA) attempted to use a RAM technology to produce a bigger RAM-based CAM system. However, the performance of this CAM system is insufficient due to the limitations imposed by RAM components, and the limited RAM bus bandwidth.
U.S. Pat. No. 5,949,696 discloses a dynamic CAM, in which each cell contains a comparator connected to the match line output. The match line output issues a first and a second logic states in response to different and similar logic states, respectively. The CAM cell also includes a first storage element having an input connected to a first data input line, and an output connected to the comparator, a second storage element having an input connected to a second data input line, and an output connected to an input of the comparator. The cell stores masked states by storing similar logic states in both storage elements. Isolation between the match line output and the storage elements is obtained by eliminating direct connection between the match line output and the storage elements.
U.S. Pat. No. 4,791,606 discloses a dynamic CAM having N and P channel transistors aligned in stripes to provide dense packing. Each cell includes a XOR-gate for comparing a stored data bit with a comparand bit. Each pair of neighboring rows and each pair of neighboring columns is arranged symmetrically to improve the packing density.
U.S. Pat. No. 5,383,146 discloses a memory array partitioned into CAM and RAM subfields by disabling the comparator in each memory cell in selected column of CAM cells to create RAM-functioning cells. The comparators in the RAM-functioning cells can be re-enabled, so that these cells may participate in subsequent comparisons to a search word. This arrangement allows direct storage and retrieval of associated data in RAM-functioning cells that correspond to data words determined to match a given search word. However, the CAM cells disclosed in the above US patents are still relatively complex and occupy large area in comparison with RAM cells of the same technology.
All the methods described above are not a satisfactory implementation of a fast, dense, large-capacity, low-power-consuming and inexpensive CAM using RAM-based technology.
It is therefore an object of the present invention to provide a method and apparatus deploying a conventional RAM cell and structure for implementing an extremely high density, low-cost per bit, high-performance and low-power-consuming CAM.
It is another object of the present invention to provide a method and apparatus for the retrieval of data stored in an associative memory at very high speed and throughput, comparable to those of state-of-the-art RAMs.
It is still another object of the present invention to provide a method and apparatus for retrieval of data stored in an associative memory which consumes low power, comparable to state-of-the-art RAMs, deploying a reduced number of power-consuming comparison units.
It is another object of the invention to provide a high-density and low-cost-per-bit associative memory deploying a reduced number of comparison units.
It is yet another object of the invention to provide an associative memory that is cost-effective, dense, and comparable in size to a RAM implemented using the same-production technology.
It is a further object of the invention to provide an associative memory that facilitates the insertion and/or the deletion of Keys and their Associated Data at a speed that meets the application requirements.
Other objects and advantages of the invention will become apparent as the description proceeds.